#!/usr/bin/env python
# -*- coding: utf-8 -*-
#functions for computing similarity and distance scores of strings

import numpy
import metrics

def edit_distance(string1, string2, distance = 0):
    """
    Computes the edit ditance from string1 to string2.
    Penalty of 1 for both gaps and mismatches, while 0 for matches.

    Args:
        string1: the first string to be compared (forms rows)
        string2: the second string to be compared (forms columns)
        distance: 0 if only returning the edit distance (default)
                  -1 if returning the actual table
                  1 if returning the tuple (table, backtraces)
    Returns:
            the edit distance between string1 and string2
            the edit distance table of string 1 and string2
            the tuple (table, backtraces)

    """
    import numpy
    #dictionary that maps table entries (x,y) to a list of their predecessors
    #of the form [(a, b, direction), ..., (n, m, direction)]
    #used to find all optimal string aligments
    backtraces = {}
    #we increment m, n by 1 to put a zero at table[0][0]
    num_rows = len(string1) + 1
    num_columns = len(string2) + 1
    #make an m by n table, where m, n are the lengths of the respective strings
    table = numpy.zeros((num_rows, num_columns))
    #initialize the first cells of each column and row
    #the values here represent the cost for just mapping to empty string
    for i in range(1, num_rows):
        table[i][0] = i
        backtraces[(i, 0)] = [(i - 1, 0, "up")]
    for j in range(1, num_columns):
        table[0][j] = j
        backtraces[(0, j)] = [(0, j - 1, "left")]
    #now we run the algorithm by looping over all the cells
    #essentially, if a path is optimal, then its subpaths will also be optimal
    #thus, at each turn, we make the transformation which invokes the least cost
    for i in range(1, num_rows):
        for j in range(1, num_columns):
            gap_row = table[i][j - 1] + 1
            gap_column = table[i - 1][j] + 1
            match = table[i - 1][j - 1] + 0
            if string1[i - 1] != string2[j - 1]:
                match += 1
            minimum = min([gap_row, gap_column, match])
            table[i][j] = minimum
            traces = []
            if gap_row == minimum:
                traces.append((i, j - 1, "left"))
            if gap_column == minimum:
                traces.append((i - 1, j, "up"))
            if match == minimum:
                traces.append((i - 1, j - 1, "match"))
            backtraces[(i, j)] = traces           
    if distance == 1:
        return table
    elif distance == -1:
        return (table, backtraces)
    return table[num_rows - 1, num_columns - 1]

def edit_distance_alignment(string1, string2):
    """
    Using the basic edit_distance function, it computes the
    optimal string alignment for two strings.
    The character "-" represents a gap.
    In case of multiple optimal alignments, it will return
    a list of all such optimal alignments.

    Args:
        string1: the first string to be aligned (via edit_distance)
        string2: the second string to be aligned (via edit_distance)
    Returns:
        the list of all optimal string alignments
        each element is the tuple (string1_aligned, string2_aligned)

    """
    import numpy
    alignments = []
    #set distance to True and align to True to get table and backtraces
    (table, backtraces) = edit_distance(string1, string2, -1)
    #we increment m, n by 1 to put a zero at table[0][0]
    num_rows = len(string1) + 1
    num_columns = len(string2) + 1
    final = max([len(string1), len(string2)]) + 1
    counter = 0
    #initialize index to final cell of table
    final_cell = (num_rows - 1, num_columns - 1)
    for cell in backtraces[final_cell]:
        edit_distance_recurse(cell, ["", ""], alignments, table, backtraces, string1, string2)
    return alignments

def edit_distance_recurse(entry, sequence, alignments, table, backtraces, string1, string2):
    """
    Recursive method for computing all optimal alignments between two strings.

    Args:
        entry: the current cell in the table
        sequence: the currently built up alignment between (string1_aligned, string2_aligned)
        alignments: the list of all optimal alignments
        table: the edit distance table between (string1, string2)
        backtraces: a dictionary containing the adjacent cells for optimal alignment
        string1: the first string being aligned
        string2: the second string being aligned
    Returns:
        nothing--this method modifies the list of alignments, which is eventually returned.

    """
    if entry[2] == "up":
        sequence[0] += string1[entry[0]]
        sequence[1] += "-"
    elif entry[2] == "left":
        sequence[0] += "-"
        sequence[1] += string2[entry[1]]
    else:
        sequence[0] += string1[entry[0]]
        sequence[1] += string2[entry[1]]
    #Base case: Backtrace leads us to first table entry
    if [entry[0], entry[1]] == [0,0]:
        #reverse the string of each sequence
        #since we walked through the table backwards
        sequence[0] = sequence[0][::-1]
        sequence[1] = sequence[1][::-1]
        alignments.append(tuple(sequence))
    #Recursive step: Continue walking through the backtraces
    else:
        for cell in backtraces[(entry[0], entry[1])]:
            new_sequence = []
            new_sequence.append(sequence[0])
            new_sequence.append(sequence[1])
            edit_distance_recurse(cell, new_sequence, alignments, table, backtraces, string1, string2)
